Internet Info 1994 March

home *** CD-ROM | disk | FTP | other *** search

/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / inet / ien / ien-187 < prev next >

Wrap

Text File | 1988-12-01 | 127KB | 4,197 lines

IEN 187 ISSUES IN INTERNETTING PART 2: ACCESSING THE INTERNET Eric C. Rosen Bolt Beranek and Newman Inc. June 1981 IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen ISSUES IN INTERNETTING PART 2: ACCESSING THE INTERNET 2. Accessing the Internet This is the second in a series of papers, the first of which was IEN 184, that examine some of the issues in designing an internet. Familiarity with IEN 184 is presupposed. This particular paper will deal with the issues involved in the design of internet access protocols and software. The issue of addressing, however, is left until the next paper in this series. Part of our technique for exposing and organizing the issues will be to criticize (sometimes rather severely) the current protocols and procedures of the Catenet, even though we do not, at the present time, offer specific alternatives in all cases. In IEN 184, section 1.4, we outlined four steps in the operation of a Network Structure. Let's now look closely at the first step, viz., how the source Host actually submits a message to the source Switch. In general, a Host will need to run three separate protocols to do this: -a protocol to utilize the electrical interface between the Host and the initial component of the Pathway it uses to access the source Switch. - 1 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen -a protocol to govern communication between the Host and the Pathway (PATHWAY ACCESS PROTOCOL). -a protocol to govern communication between the Host and the source Switch (NETWORK ACCESS PROTOCOL). We can make this point more concrete by giving some examples. Consider the case of an ARPANET host which wants to access the Catenet via the BBN gateway (which is also a Host on the ARPANET). Then the ARPANET is the Pathway the host uses to access the source Switch (the gateway). If the host is a local or distant host, the electrical interface to the Pathway is the 1822 hardware interface. If it is a VDH host, the electrical interface is whatever protocol governs the use of the pins on the modem connectors. If it were an X.25 host, the interface might be X.21. The PATHWAY ACCESS PROTOCOL is the 1822 protocol, which governs communication between the host and the first IMP on the Pathway. The NETWORK ACCESS PROTOCOL in this case would be the DoD standard Internet Protocol (IP), which governs communication between the host and the source Switch (gateway). If, on the other hand, we consider the case of an ARPANET host which is communicating with another host on the ARPANET, and whose data stays purely within the ARPANET, 1822 becomes both the NETWORK ACCESS PROTOCOL (since the source Switch is now identical to the source IMP), and the PATHWAY ACCESS PROTOCOL, since the Pathway is now the 1822 hardware connection. - 2 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen We will have nothing further to say about the electrical interface, since that is really just a straightforward hardware matter. (However, such characteristics of the electrical interface as error rate, for example, might have to be reflected in the design of the Pathway Access Protocol.) The design of both the Pathway Access Protocol and the Network Access Protocol do raise a large number of interesting issues, and that shall be the focus of this paper. We believe it to be very unlikely that Host software (or gateway software) can utilize the internet efficiently unless it takes the idiosyncrasies of BOTH the Pathway Access Protocol and the Network Access Protocol into account. A gateway or host software implementer who spends a great deal of time carefully building his IP module, but who then writes a "quick and dirty" 1822 module, is likely to find that his inefficient use of 1822 completely sabotages the advantages which his carefully designed IP is supposed to have. Experience with the ARPANET has shown many times that poorly constructed host software can create unnecessary performance problems. It seems, for example, that many 1822 modules completely ignore the flow control restrictions of the ARPANET, thereby significantly reducing the throughput that they can obtain over the ARPANET. We have even encountered many hosts which cannot properly handle some of the control messages of the 1822 protocol, which also leads to a very inefficient use of the ARPANET. - 3 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen It is not difficult to understand why a host (or gateway) software implementer might overlook the issues having to do with the proper use of the Pathway Access Protocol. There are a number of pressures that, if not dealt with properly at a management level, lead naturally to the neglect of Pathway Access Protocol issues. An internet implementer might want to concentrate on the "new stuff", viz., the Network Access Protocol, IP, and may not be at all interested in the idiosyncrasies of the older Pathway Access Protocol (1822). He might be misled, by the belief that the packet-switching networks underlying the internet should be transparent to it, into believing that those packet-switching networks can be treated as simply as if they were circuits. He might also be under pressure to implement as quickly as possible the necessary functionality to allow internet access. While this sort of pressure is very common, the pressure to make the internet PERFORM well (as opposed to the pressure simply to make it work at all) is generally not felt until much (sometimes years) later. The tendency to neglect performance considerations while giving too much attention to simply obtaining the needed functionality in the quickest way is also reinforced by such "modern" design procedures as top-down design, and specification of protocols in formal languages. While these procedures do have a large number of advantages, they also serve to obscure performance issues. If the researchers and designers of protocols, following modern - 4 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen design methodologies, do not give adequate consideration to performance at the time of protocol design, one can hardly expect the implementers to do so. Yet ARPANET experience has shown again and again that decisions made at the level of implementation, apparently too picayune to catch the attention of the designers, can be important determinants of performance. Still another reason why protocol software implementers might tend to disregard the niceties of the Pathway Access Protocol is the lack of any adequate protocol software certification procedure. An ARPANET host could be connected to an IMP for months, transferring large amounts of traffic, without ever receiving certain 1822 control messages. Then some sort of change in network conditions could suddenly cause it to receive that control message once per hour. There really is no way at present that the implementer could have possibly run tests to ensure that his software would continue to perform well under the new circumstances. This problem is somewhat orthogonal to our main interests, but deserves notice. One of the most important reasons why protocol software implementers tend to ignore the details of the Pathway Access Protocols is the "philosophical" belief that anyone working on internet software really "ought not" to have to worry about the details of the underlying networks. We will not attempt to refute this view, any more than we would attempt to refute the view of a person who claimed that it "ought not" to rain on his - 5 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen day off. We emphasized in IEN 184 that the characteristics of a Network Structure's Pathways are the main thing that distinguish one Network Structure from another, and that the problems of internetting really are just the problems of how to build a Network Structure with Pathways as ill-behaved as packet-switching networks. Thus building a successful internet would seem to be a matter of dealing specifically with the behavior of the various Pathways, rather than ignoring that behavior. We assume that that our task is to create an internet which is robust and which performs well, as opposed to one which "ought to" perform well but does not. It is true, as we have said, that within the Network Structure of the Catenet, we want to regard the ARPANET as a Pathway whose internal structure we do not have to deal with, but that does NOT mean that we should regard it as a circuit. Any internet Host or Switch (gateway), TO PERFORM WELL, will have to have a carefully designed and tuned Pathway Access Protocol module geared to the characteristics of the Pathway that it accesses. The relationship between the Pathway Access Protocol and the Network Access Protocol does offer a number of interesting problems. For one thing, it appears that these protocols do not fit easily into the OSI Open Systems model. If we are accessing a single packet-switching network, the Network Access Protocol appears to be a level 3 protocol in the OSI model, and the Pathway Access Protocol appears to be a level 2 protocol. - 6 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen However, if we are accessing an internet, we still need the level 3 Network Access Protocol, but now the Pathway Access Protocol also has a level 3 component, in addition to its level 2 component. So the Host is now running two different level 3 protocols, although the Network Access Protocol appears functionally to be in a layer "above" the level 3 part of the Pathway Access Protocol. Perhaps the main problem here is that the OSI model has insufficient generality to capture the structure of the protocols needed to access an internet like the Catenet. It is interesting to see how some of these considerations generalize to the case of a Host which needs to access an internet (call it "B") through a Pathway which is itself an internet (call it "A"). Then the Host needs a Network Access Protocol for the internet B, a Network Access Protocol for the internet A (which is also its Pathway Access Protocol for internet B), and a Network Access Protocol for the actual network to which it is directly connected, which is also its Pathway Access Protocol for internet A. As we create more and more complicated Network Structures, with internets piled on top of internets, the Hosts will have a greater and greater protocol burden placed upon them. Ultimately, we might want to finesse this problem by removing most of this burden from the Hosts and putting it in the Switches, and giving the Switches knowledge of the hierarchical nature of the (internet) Network Structure. For - 7 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen example, a Host on the ARPANET might just want to give its data to some IMP to which it is directly connected, without worrying at all about whether that data will need to leave the ARPANET and travel via an internet. The IMP could decide whether that is necessary, and if so, execute the appropriate protocol to get the data to some internet Switch at the next highest level of hierarchy. If the data cannot reach its destination within the internet at that level, but rather has to go up further in the hierarchy to another internet, the Switch at the lower level could make that decision and execute the appropriate protocol. With a protocol structure like this, we could have an arbitrarily nested internet, and the Switches at a particular level, as well as the Hosts (which are at the lowest level), would only have to know how to access the levels of hierarchy which are immediately above and/or below them. This procedure would also make the host software conform more to the OSI model, since only one Network Access Protocol would be required. However, this sort of protocol structure, convenient as it might be for the Hosts, does not eliminate any of the issues about how to most efficiently use the Pathways of a Network Structure. Rather, it just pushes those issues up one level, and makes the Switches correspondingly more complicated. A proper understanding of the issues, therefore, is independent of what sort of protocol structuring we design. - 8 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen Having emphasized the need for hosts and gateways to take account of the details of particular Pathway Access Protocols, we must point out that this is not always a simple thing to do. If the Network Structure underlying a Pathway is just a single network, like the ARPANET, this problem is not so terribly difficult, since one can expect that there will be available a lot of experience and information about what a host should do to access that network efficiently. If, on the other hand, the Pathway is really an internet itself, the problem is more difficult, since it is much more difficult to say anything substantive about its characteristics. This is a point we must keep in mind as we discuss specific issues in access protocol design. In the remainder of this paper, we will attempt to deal with a number of issues involved in the design of robust, high-performance Network and Pathway Access Protocols. We will not attempt to cover every possible issue here. In particular, the issue of how to do addressing is important enough to warrant a paper of its own, and shall be put off until the next paper in this series. We will attempt throughout to focus on issues which particularly affect the reliability of the internet configuration (as perceived by the users), and on issues which affect the performance of the internet (as perceived by the users). Wherever possible, we will try to exhibit the way in which the reliability and performance of a protocol trade off against its - 9 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen functionality. If protocol designers concentrate too heavily on questions of what functionality is desired, as opposed to what functionality can be provided at a reasonable level of performance and reliability, they are likely to find out too late that the protocol gives neither reasonable performance nor reliability. 2.1 Pathway Up/Down Considerations In general, a Host will be multi-homed to some number of Switches. In fact, it is easy to imagine a Host which is both (a) multi-homed to a number of IMPs, within the Network Structure of the ARPANET (this cannot be done at present, but is planned for the future), and also (b) multi-homed to a number of gateways (namely, all the gateways on the ARPANET) within the Network Structure of the Catenet. Whenever a Host is multi-homed to a number of Switches in some Network Structure, it has a decision to make, namely, which of those Switches to use as the source Switch for some particular data traffic. In order to make this choice, the very first step a Host will have to take is to determine which Switches it can reach through operational Pathways. One thing we can say for sure is that if a Host cannot reach a particular Switch through any of its possible Pathways, then it ought not to pick that Switch as the source Switch to which to send its data. In a case, for example, where the ARPANET is partitioned, a Host on the ARPANET which needs to send - 10 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen internet traffic will want to know which gateways it can reach through which of its ARPANET interfaces. To make this determination possible, there must be some sort of "Pathway Up/Down Protocol", by which the Host determines which of its potential Pathways to gateways are up and which are down. This is not to say, of course, that the Hosts have to know which gateways are up and which are down, but rather, they must know which gateways they can and cannot reach. Of course, this situation is quite symmetric. The Switches of a Network Structure (and in particular, the gateways of an internet) must be able to determine whether or not they can reach some particular host at some particular time. Otherwise, the gateway might send traffic for a certain Host over a network access line through which there is no path to that Host, thereby causing unnecessary data loss. Apparently, this problem has occurred with some frequency in the Catenet; it seems worthwhile to give it some systematic consideration. The design of reliable Pathway Up/down protocols seems like something that "ought to be" trivial, but in fact can be quite difficult. Let's begin by considering the case of an ARPANET host which simply wants to determine whether it can reach some IMP to which it is directly connected. The first step for the host to take (if it is a local or distant host) is to look at the status of its Ready Line. If the Ready Line to some IMP is not up, then it is certain that communication with that IMP is not - 11 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen possible. If the host is a VDH host, then there is a special up/down protocol that the host must participate in with the IMP, and if that fails, the host knows that it cannot communicate with the IMP. Of course, these situations are symmetric, in that the IMP has the same need to know whether it can communicate with a host, and must follow the same procedures to determine whether this is the case. However, even in these very simple cases, problems are possible. For example, someone may decide to interface a host to an IMP via a "clever" front-end which hides the status of the Ready Line from the host software. If a host is multi-homed, and has to choose one from among several possible source IMPs, but cannot "see" the Ready Lines, what would stop it from sending messages to a dead IMP? Eventually, of course, a user would notice that his data is not getting through, and would probably call up the ARPANET Network Control Center to complain about the unreliability of the network, which, from his perspective, is mysteriously dropping packets. From the opposite perspective, one must realize that such a front-end might also hide the status of the host from the IMP, so that the network has no way of knowing whether a particular host is currently capable of communicating with the network. This is especially likely to happen if the "clever" front-end takes packets from the network which are destined for a particular host, and then just drops them if the host is down, with no feedback to either IMP or host. If a host is multi-homed, but one of its access lines is down, - 12 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen this sort of configuration might make it quite difficult for the network to reach a reasonable decision as to which access line to use when sending data to that host. The lesson, of course, is that the status of the Ready Line should never be hidden from the host software, but it is hard to communicate this lesson to the designers of host software. Again, the issue is one of performance vs. functionality. A scheme which hides the status of the Ready Line from IMP or host may still have the required (minimum) functionality, but it will just perform poorly under certain conditions. This may seem like a made-up problem which probably would never occur, but in fact it has occurred. We once had a series of complaints from a user who claimed that at certain times of certain days he had been unable to transmit data successfully over the ARPANET. Upon investigation, we found that during those times, the user's local IMP had been powered down, due apparently to a series of local power failures at the user's site. Of course, the IMP will not transmit data when it is powered down. But it was somewhat mysterious why we had to inform someone of a power failure at his own site; surely the host software could have detected that the IMP was down simply by checking the Ready Line, and so informed the users. When this user investigated his own host software (a very old NCP), he found that it would inform the users that the IMP was down ONLY if the IMP sent the host a message saying that it was going down. Since the IMP does not - 13 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen send a message saying that it is about to lose power, the host software, which apparently did not check the Ready Line as a matter of course, did not detect the outage. It looked to the user, therefore, as though the network had some mysterious and unreliable way of dropping packets on the floor. It seems that many hosts presently exist whose networking software is based on the assumption that the IMPs never go down without warning. Hosts do sometimes have difficulty determining whether their Pathway to an IMP is up or down, even when it seems like this should be totally trivial to determine. Reliable network service requires, however, that host software and hardware designers do not hide the status of the IMP from the host, or the status of the host from the IMP. This will become increasingly important as more and more hosts become multi-homed. Of course, this is only a first step in a proper up/down determination. It is not impossible for a Ready Line to be up but for some problem either in IMP or host to prevent communications from taking place. So some higher level up/down protocol is also necessary. Some protocol should be defined by which Host and Switch can send traffic to each other, and require the other to respond within a certain time period. A series of failures to respond would indicate that proper communications is not possible, at least for the time being. It is important to note, though, that the need for a higher level up/down protocol does not obviate the need for the lower level procedure of - 14 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen monitoring the Ready Line. If the higher level procedure fails, but the Ready Line appears to be up, knowledge of both facts is needed for proper fault isolation and maintenance. Also important to notice is that if the lower level procedure indicates that the Pathway is down, the higher level procedure should not be run. This might not seem important at first glance, but in practice, it often turns out that attempting to send traffic to a non-responsive machine results in significant waste of resources that could be used for something more useful. In the more general case, where a Host's Pathway to a source Switch may include one or more packet-switching networks, it is far from trivial to determine whether the Switch can be reached from the Host via the Pathway. Consider, for example, how a given ARPANET host could determine whether a given Catenet gateway on the ARPANET can be accessed via some given ARPANET source IMP. Of course, the first step is to determine whether communication with that source IMP is possible. Even if it is, however, the gateway might still be unreachable, since it may be down, or the network may be partitioned. ("Officially", every ARPANET Host is supposed to be reachable from any other ARPANET Host. However, the average connectivity of the ARPANET is only 2.5, which means that only a small number of line or node failures are needed to induce partitions. Furthermore, a few ARPANET sites are actually stubs, which means that a single failure can isolate them from the rest of the ARPANET. As often - 15 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen seems to happen in practice, the sites that are stubs seem to be attached by the least reliable lines, so that partitions are not infrequent. At any rate, there will probably be networks in the internet that partition more frequently than the ARPANET does. Internet protocols must detect and react to network partitions, instead of simply disregarding them as "too unlikely to worry about." ) In the special case where the Pathway between some Host and some Switch is the ARPANET, the ARPANET itself can provide information to the Host telling it whether the Switch is reachable. If the Switch is not reachable, and a Host attempts to send an ordinary data packet to it, the ARPANET will inform the Host whether or not that packet was delivered, and if not, why not. Unfortunately, the current ARPANET does not provide this information in response to datagrams. However, we have already seen the need to provide such information in the case of logically addressed datagrams (see IEN 183), and plan to implement a scheme for doing so. An ARPANET Host which is also an internet Host can implement a low level Pathway up/down protocol simply by paying attention to the 1822 replies that it receives from the ARPANET. There are hosts which seem to disregard these 1822 control messages, and which seem to continue to send messages for unreachable hosts into the ARPANET. Of course, this is a senseless waste of resources which can severely degrade performance. Indeed, it may look to an end-user, or even - 16 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen a gateway implementer, as though the ARPANET is throwing away packets for no reason, when the real problem is that the host software cannot respond adequately to exceptional conditions reported to it by the network. We have spoken of the need for Host and Switch to run a higher level up/down protocol, to take account of the conditions when one of them seems reachable to the network, but still will not perform adequately when another entity attempts to communicate with it. Switch and Host must run some protocol together which enables each to validate the proper performance of the other. The Catenet Monitoring and Control System (CMCC), currently running on ISIE, runs a protocol of this sort with the gateways. The CMCC sends a special datagram every minute to each gateway, and expects to receive an acknowledgment (or echo) for this special datagram back from the gateway. After three consecutive minutes of not receiving the echo, the CMCC infers that the gateway cannot be reached. After receiving a single echo, the CMCC infers that the gateway can be reached. (Gateways run a similar protocol with their "neighboring gateways".) A Pathway up/down protocol which does not rely on the intervening network to furnish the information would certainly have to involve some such exchange of packets between the Host and the Switch, but it would have to be rather more complex than this one. One of the problems with this protocol is that it is incapable of detecting outages of less than three minutes. This - 17 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen may be suitable for the CMCC's purposes, but is not generally suitable for a Host which wants to know which source Switch to send its traffic to. We would not want some Host to spend three full minutes sending data to a Switch which cannot be reached; the effect of that could be many thousands of bits of data down the drain. (Of course, higher level protocols like TCP would probably recover the lost data eventually through the use of Host-Host retransmissions, but that involves both a severe drain on the resources of the Host, which ought to be avoided whenever possible, and a severe degradation in delay and throughput.) Another problem with this particular protocol is that it uses datagrams, which are inherently unreliable, and as a result, the inference drawn by the CMCC is unreliable. From the fact that three datagrams fail to get through, it is quite a big jump to infer that no traffic at all can get through. Another problem is the periodicity of the test packets. If they get in phase with something else which may be going on in the network, spurious results may be produced. The design of a Pathway up/down protocol must also be sensitive to the fact that some component network of a Pathway may be passing only certain types of packets and not others. For example, at times of heavy usage, certain networks may only be able to handle packets of high priority, and lower priority packets may either be refused by that net (at its access point), or, even worse, discarded internally by the net with no feedback. - 18 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen The Pathway up/down protocol must be sensitive to this, and will have to indicate that the Pathway is only "up" to certain classes of traffic. If a Pathway is really a Network Structure which will inform its Hosts when it cannot accept certain traffic types, then this information can be fed back into the up/down protocol. (Note however that this might be very difficult to do if the Pathway consists of not a single network, but of an internet). Alternatively, a Host may have to rely on its higher level Pathway up/down protocol to determine, for several classes of traffic, whether the Pathway is up to members of that class. Apart from the inherent difficulty of doing this, it may be difficult to map the traffic classes that a given component network distinguishes into traffic classes that are meaningful to a Host, or even to the Switches of the internet. Yet we wouldn't want traffic to be sent into a network which is not accepting that particular kind of traffic, especially if there are alternative Pathways which would be willing to accept that traffic. Many of these considerations suggest that the higher level up/down protocols could turn out to be rather intricate and expensive. Remember that a gateway may have many many hosts "homed" to it, and must be able to determine, for each and every one of these hosts, whether communication with it is possible. Yet it probably is not feasible to suppose that each gateway can be continuously running an up/down protocol with each potential - 19 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen host, and still have time left to handle its ordinary traffic. This suggests that the primary up/down determination be made from the low-level protocol, i.e., that the Switches should rely on the networks underlying the Pathways to inform them whether a given Host is up or down, and the Hosts should similarly rely on the networks underlying the Pathways to pass them status information about the gateways. It would be best if the higher level up/down protocol only needed to be run intermittently, as a check on the reliability of the lower level protocol. Unfortunately, the use of low level up/down protocols is not always possible. Many networks, unlike the ARPANET, do not even gather any information about the status of their hosts, and hence cannot inform a source Host that it is attempting to send data to a destination Host which is not reachable. (SATNET is an example of a network that does not pass "destination dead" information.) In the case where a particular Host-Switch Pathway is itself an internet, the problem is even worse. Unless the component networks of that internet can be made to cooperate in obtaining RELIABLE up/down information and passing it back to the source Host, it will be very hard for a Host to make any reasonable determination as to whether a particular Switch is reachable. We would strongly recommend the incorporation of low level up/down protocols in ALL component networks of the internet. There is another important problem in having a Host determine which of its potential source Switches on the internet - 20 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen are up and which are down. In order to run a protocol with the Switch, or even to query the lower level network about the Switch, the Host must have some way of identifying the Switch. It is not so difficult for a Host on the ARPANET to identify the IMPs that it is directly connected to, since it is quite simple to devise a protocol by which a Host can send a message down each of its access lines, asking who is on the other end. It is rather more difficult for a Host to find out which gateways it is homed to (i.e., which gateways are on a common network with it). There is no easy way for an ARPANET Host to find out which other ARPANET hosts are Catenet gateways. There is no "direct connection" at which to direct protocol messages. In the current Catenet, hosts have to know in advance how to identify the Catenet gateways on their networks (although there are certain restricted circumstances under which a host can obtain the name of another gateway from a gateway about which it already knows). Yet it does not seem like a good idea to require a Host to know, a priori, which other Hosts on its network are also internet Switches. This makes it difficult to enable Hosts to take advantage of newly installed gateways, without making changes by hand to tables in the Hosts (a procedure which could require weeks to take effect). There is a rather attractive solution to this problem. If each component network in the internet can determine for itself which of its Hosts are also internet Switches (gateways), then the Switches of that network can - 21 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen provide that information to the Hosts. This would require the existence of a protocol which the gateways run with the Switches of the individual component networks, by means of which the gateways declare themselves to be gateways. Each individual network would also have to have some internal protocol for disseminating this information to other Hosts, and for keeping this information up to date. If the network allows GROUP ADDRESSING, further advantages are possible. The network could maintain a group address (called, say, "Catenet Gateways") which varies dynamically as gateways enter and leave the network. Hosts could find out which gateways are reachable over particular network access lines by sending some sort of protocol message to the group address, and waiting to see who replies. Hosts would then not have to have any a priori knowledge of the gateways on their home networks. One very important though often neglected aspect of up/down protocols is the way in which the up/down protocol interacts with the ability to perform adequate maintenance of the Network Structure. It is tempting to think that a Pathway up/down protocol ought to declare a Pathway "down" only if it is totally dead or otherwise totally unusable. But in fact, a pathway should be declared down before it becomes totally dead, if its packet "non-delivery rate" exceeds a certain threshold. (We use the term "non-delivery rate" where the term "error rate" is more commonly used. We are trying to emphasize that it is important - 22 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen to detect not only errors, in the sense of checksum errors, but rather any circumstances, including but not limited to checksum errors, which prevent the proper delivery of packets.) There are two reasons for this: 1) The existence of a non-zero non-delivery rate on a Pathway implies that some packets placed on that Pathway will not make it through to the other end. In most applications, these packets will have to be retransmitted at some higher level of protocol, or else by the end user himself (packetized speech is one of the few exceptions to this). As the number of retransmissions increases, the delay also increases, and the throughput decreases. So when the non-delivery rate reaches a certain point, the Pathway should be removed from service, in order to improve delay and throughput. Of course, this assumes that an alternate Pathway is available with a lower non-delivery rate. Also, other things being equal, removing bandwidth from a Network Structure will also tend to increase delay and reduce throughput, so we really want the up/down protocol to pick out the proper cross-over point. 2) It is often better to fix a Pathway at the first sign of trouble than to wait for it to fail totally. One implication of this is that the up/down protocol should - 23 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen perform equally well whether or not the Pathway is heavily loaded with traffic. We would not want to use a protocol which made its determination solely by making measurements of user traffic, since that protocol would not function well during periods when user traffic is very light. That is, a faulty Pathway with no user traffic would not be detected. Yet if repair work has to be done on a Pathway, we would most like to find out about it during lightly loaded hours, so that a fix can be effected with minimal disruption, possibly before the heavily loaded hours begin. Another important characteristic for a Pathway up/down protocol to have is the ability to determine the nature of the Pathway "outage". This is quite important for fault isolation, but is easy for a host software person to overlook, since he may not be aware of such issues. If a Host cannot get its packets to a Switch over a certain Pathway, it will want to regard that Pathway as down, and will want to use an alternate Pathway. From the Host perspective, it doesn't care whether the reason it can't use the Pathway is because of a network partition, or because of network congestion, or because of some other reason. However, if the Host personnel want to be able to call up the Pathway personnel and request that the problem be fixed, it's not enough to say, "Your network isn't working; call me back when it's fixed." The more information the Pathway up/down protocol can - 24 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen gather, the quicker a fix can be effected. In the case where the Pathway is the ARPANET, quite a bit of information can be gathered from proper instrumentation of the 1822 module, and proper attention by the host software to the 1822 replies; this will be discussed further in section 2.6. The design of the ARPANET's line up/down protocol might be a good model for the design of a general Pathway up/down protocol. The design of the ARPANET protocol was based upon a mathematical analysis of the probabilistic error characteristics of telephone circuits, and the protocol is intended to bring a line down when and only when its error rate exceeds a threshold. However, the error characteristics of Pathways in general (i.e., of packet-switching networks) are not well understood at all, and there is no similar mathematical analysis that we can appeal to. At present, we can offer no ready answer to the question of how a Host can tell which of several possible source Switches is reachable, if the Switches are accessed via a network (or sequence of networks) which will not even inform the Host whether or not its traffic even gets delivered. This is an important question which will require further thought, and considerable experimentation. - 25 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen 2.2 Choosing a Source Switch Once a Host has determined which source Switches it can reach over which of its interfaces, it still has to determine which one to use for sending some particular packet (unless the Host is "lucky" enough to find out that only one source Switch is reachable). Making the proper choice can be quite important, since the performance which the Host gets may vary greatly depending upon which source Switch it selects. That is, some source Switch might be much closer to the destination, in terms of delay, than another. It then might be quite important to choose the proper one. To make things a bit more concrete, consider the case of a Host which is multi-homed (via several distinct 1822 links) to several ARPANET IMPs, and whose traffic can be handled entirely within the ARPANET. There are several things a host might want to take into account in choosing the best source IMP to use for a particular packet, including: 1) The loading on the 1822 access line to each possible source IMP. 2) The distance between each source IMP and the destination Host, for some notion of "distance." The first of these two quantities is relatively easy to obtain, since all the Host need do is monitor its own 1822 lines; it should be possible to devise a monitoring scheme which - 26 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen indicates which of the 1822 lines is providing the best service to its IMP, perhaps simply by measuring the queuing delay experienced in the Host by messages queued for that line. (Any such measurement would have to take into account some of the niceties of the 1822 protocol, though.) Obtaining information about the second quantity is more difficult. The Host might try to keep some measurement of round-trip delay (delay until a RFNM is received) between itself and each destination Host. However, in order to do this, some traffic for each destination Host would have to be sent over each access line, so that the delay could be measured. This means that some traffic has to be sent over a long delay path, simply in order to determine that that is a long delay path. A simpler scheme might be for the Host to get delay information from the IMP. A Host could ask each potential source IMP what its delay to the destination Host is. By using this information, plus the information it gathers locally about the loading of its access lines, the Host could determine which source IMP provides the shortest path to the destination. This would require that we define a protocol by which a Host can ask the IMPs to which it is homed to provide their delays to a destination Host. The Host could make these requests periodically, and then change its selection of source IMPs as required in order to react to changes in delay. There are a few subtle protocol issues to be considered here, though. We would have to make sure that a Host cannot beat a Switch to death by - 27 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen constantly asking it what its delays are; probably we would have to give the Switch the option of not replying to these requests if it is too busy with other things (like ordinary data traffic). A bigger problem lies in the assumption that the Switches will even have this data to provide. The routing algorithm used by the ARPANET IMPs does, in fact, provide each IMP with a value of delay, in milliseconds, to each other IMP in the network. There is no reason why this information could not be fed back to the hosts on request. Note, however, that while a source IMP knows its delay to each possible destination IMP, it does not know its delay to each potential destination HOST over each possible access line to that Host, since the routing algorithm does not maintain measurements of delay from an IMP to a locally attached host. Yet this latter delay might be quite significant. Still, the information that the ARPANET IMPs could provide to the Hosts should enable them to make a better choice than they could make without this information. Another problem with this idea of having the Switches feed back delay information to the Hosts is the proper choice of units. If a Host is going to take the delay information provided by the network and then add some locally measured delay information to it, it is important for the Host to know what units the network is using to measure delay. Yet we also have to ensure that the network developers and maintainers are free to change the way in which the network does measurements, and the - 28 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen units in which the measurements are taken, WITHOUT NEEDING TO COORDINATE SUCH CHANGES WITH ALL HOST ADMINISTRATIONS. That is, we don't want further development of the network, and further refinements in the way network measurements are done, to be overly constrained by the fact that the Hosts demand measurements in a certain unit. We also want to ensure that host software implementations are not invalidated by a decision to change the units that the network uses for its internal measurements. So the protocol would have to enable the Switch to tell the Host what units it is providing; the Host would then make any necessary conversions. (Alternatively, the Host could tell the Switch what units it wants, and the Switch could do the conversion before sending the information to the Host.) In the internet environment, the situation is more complicated. An ARPANET Host which is also an internet Host would have to (a) figure out its delay to each of its source IMPs, (b) query each source IMP for its delay to each source gateway, and (c) query each source gateway about its delay to each destination. There is no straightforward way to gather the rest of the needed delay information, however, namely the delay from the destination gateway to the destination Host. In more complex Network Structures, with internets nested on top of internets, this problem becomes increasingly more complex. It seems that the only really reliable way, and the most straightforward way, for the source Host to gather information - 29 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen about the delays via various source Switches to a destination Host, is for it to do the measurements itself. This is the recommended solution. Delay information should also be made available from the component networks for Hosts which cannot do this, but it should be understood that those hosts cannot expect to get as good a quality of service as the hosts which go to more trouble to do their own measurements. 2.3 Type of Service One very important piece of information that a Host must specify to the source Switch through the Network Access Protocol is the "type of service" desired. To quote from the DoD standard Internet Protocol (IP) specification [1, p. 15], "The Type of Service is used to indicate the quality of the service desired; this may be thought of as selecting among Interactive, Bulk, or Real Time, for example." This seems to make sense, since one does have the feeling that different types of applications will fall into different categories, and information about the categories may help the Switches of the Network Structure through which the data is moving decide how best to treat it. However, choosing just the right set of categories of service is quite a complex matter. For example, both a terminal user of a time-sharing system, and a user of a query-response system (like an automated teller) fall under the rubric of "interactive", but that doesn't mean that the service requirements are the same. - 30 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen Both Remote-Job-Entry and File Transfer fall under the rubric of "bulk", but it is not obvious that they have the same requirements. Both real-time process control and packetized voice fall into the category of "Real Time", but the requirements of these two applications seem to be very different. A very real issue, which has not yet been given adequate consideration, is the question of just how many categories of application type there really should be, and just what the implications of putting a packet into one of these categories ought to be. As we go on, we will see a number of problems that arise from failure to carefully consider this issue. It is rather difficult to find examples of Network Access Protocols which have really useful class-of-service selection mechanisms. The 1822 protocol allows the user to select from among two priorities; it allows the choice of single-packet or multi-packet messages; it allows the choice between "raw packets" and "controlled packets." It is up to some user (or more realistically, up to some host software implementer who may have only a vague and limited understanding of the applications which his software will serve, and of the network that he is accessing) to map his application characteristics onto these three choices. Unfortunately, it is doubtful that there is anyone outside of the ARPANET group at BBN with any clear understanding of the implications of making the various choices. The task of making the optimum choice for some application is further complicated by - 31 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen the fact that the effects of making the various choices can be very dependent on the network load. For example, it is often possible to get more throughput from single-packet messages than from multi-packet messages. This will happen if the destination IMP has several different source Hosts sending multi-packet messages to it, but is short on buffer space (as many of the ARPANET IMPs are), and if the multi-packet messages contain only two or three packets per message. Not only is this sort of thing very difficult for an arbitrary user to understand (to a naive network user, it must seem ridiculous), it is also subject to change without notice. Although users can vary their service significantly by sending optimum size messages, the principles governing the "optimum" size are very obscure, and we cannot really expect users to map their application requirements onto this network feature in any reasonable manner. A similar problem arises with respect to the priority bit that the 1822 protocol allows. Basically, a priority packet will get queued ahead of any non-priority packets on the queues for the inter-IMP links and on the queues for the IMP-Host access lines. However, priority packets receive no special preference when competing with non-priority packets for CPU cycles or for buffer space. Also, there is no notion at all in the ARPANET of refusing to accept low priority packets because the network is already too heavily loaded with high priority packets. Although someone who has carefully studied the ARPANET might be able to - 32 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen say what the effect of setting the priority bit is under some particular set of circumstances, some user who is wondering whether his application requirements are best served by setting the priority bit really has no way of answering that question. The actual effect of the priority bit does not fully correspond to any intuitive notion of priority that an arbitrary user is likely to have. Another problem: although it is presently allowed, it is not really a good idea to let the users choose whether to set the priority bit or not. Fortunately, most hosts do not submit packets with the priority bit on. It wouldn't be terribly surprising, though, if some host software implementer decided that he would always set the priority bit, in order to get faster service. Of course, overuse of the priority bit just means that it will have no effect at all, and that seems to mean that its use must be controlled in some way, and not simply left up to each user, as in the 1822 protocol. The IP offers even worse problems than 1822 in these respects. Like 1822, the IP does not really allow the user to classify his traffic according to application type. Rather, it forces him to pick one of 5 possible precedence values (from highest to lowest precedence, whatever that means, exactly), to pick one of 4 reliability values (from most to least reliable), to indicate whether he wants his data to be stream data or datagram data in component networks for which this distinction is meaningful, to indicate whether he wants high or low speed, and - 33 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen to indicate whether speed is more important to him than reliability is. The idea here, apparently, is that any user can map his application requirements into certain abstract properties, and the information which the IP passes from the Host to the source Switch is supposed to indicate which of these abstract properties the user needs. At each internet hop, these abstract properties are supposed to be mapped to particular properties that are meaningful to the network in question. The Pathway Access Protocol for that network would then be used to indicate to the Switches of that component network what particular properties the data transfer should have within that network. In fact, the only apparent use of the "type of service" information in the internet Network Access Protocol (IP) is to carry information to be passed to the individual Pathway Access Protocols. This all sounds reasonable enough when considered in the abstract, but it gives rise to a large number of vexing problems when we attempt to consider particular ways in which this "type of service" information is to be used. Empirically, it seems that few current gateway implementations take any notice of this information at all. We suggest that the problem is not that the individual implementers have not had time to write the code to take account of this information, but rather that it is far from clear how this information should be handled, or even that this information is really meaningful. We suggest further that an - 34 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen internet user would also have a great deal of difficulty deciding how to specify the "type of service" information in order to get a specific quality of service needed by his application. Suppose a user needs the maximum possible speed for his application, so he uses IP to indicate that he values speed above all else. What would the current Catenet do? For concreteness, suppose there is a choice of sending this user's data either via a sequence of 4 low-delay terrestrial networks, or through three satellite networks, each of which contains two satellite hops. The current implementation of the Catenet would send the data through the three satellite networks. However, since the user indicated that he values speed above all else, he will get the fastest service that each of the satellite networks can provide! Of course, this may not be what the user will have expected when he asked for speed, since the fastest service through a satellite network is not fast. A user may well wonder what the point of specifying speed is, if his data is going to traverse some sequence of satellite networks, even if a much faster path is available. Furthermore, it is not correct to assume, in general, that a user who values speed will really want the speediest service through every network. If traffic must go through a satellite network, it may be important to try to get one-hop rather than two-hop delay, if this is possible. Yet it may not be economical to also try to get the speediest service through all terrestrial networks; the difference between high and low - 35 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen speed service through a terrestrial network might be "in the noise", even when compared to the shortest delay through the satellite network. It is not impossible, or even unlikely, that better overall service (or more cost-effective service) can be achieved by using the fastest possible service through some networks, but less than the fastest through others. There are two immediate lessons here. First, the characteristics that a user specifies in the Network Access Protocol may require some interaction with routing, since the characteristics he desires simply cannot be provided, in general, by sending his traffic through a random series of networks, and then mapping information he specifies in the Network Access Protocol into information carried in the individual Pathway Access Protocols. Second, what a user means intuitively by "speed" just may not map into what some particular component net means by "speed". Once again, we see that the basic problem stems from the differing characteristics of the Pathways in the Network Structure. Another peculiar feature of the IP is the mysterious "S/R bit", which a user is supposed to set to indicate whether he prefers speed over reliability, or vice versa, should these conflict. One unsuitable aspect of this is the apparent assumption that it even makes sense to prefer either speed or reliability over the other, without specifying more detail. It is easy to imagine that some user is willing to accept reliability of less than 100% if he can increase his speed - 36 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen somewhat. It is also easy to imagine that a user would be willing to accept somewhat slower service if it gives him higher reliability. But there will always be a range that the user wants to stay within. If his reliability must be moved below a certain threshold in order to get more speed, he may not want this, even if he would be willing to say that he prefers speed to reliability. Similarly, if his delay must go above a certain threshold to gain more reliability, he may not want this, even if, when talking in general terms, he says that he needs reliability more than speed. It really doesn't make any sense at all to try to map a particular application type into "speed over reliability" or "reliability over speed", unless ranges and thresholds are also specified. What this means in practice is that a user will not be able to make a reasonable choice of how to set this bit in the IP header; whatever he sets it to is bound to produce results other than those he expects under some not too uncommon set of circumstances. We do not want to leave unquestioned the tacit assumption that speed and reliability are opposing virtues, so that increasing one must be expected to decrease the other. To quote again from the IP spec, "typically networks invoke more complex (and delay producing) mechanisms as the need for reliability increases" [1, p 23]. This reasoning is somewhat superficial. It may be true that in some networks, the less reliable kinds of service are speedier, but this is not invariably the case. To - 37 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen see this, consider the following (fictitious) network. This network allows the user to request either "reliable" or "unreliable" data transfer. Reliable packets are controlled by a set of protocols, both at the end-end and hop-hop level, which ensure delivery. Unreliable packets are not under the control of any such protocols. Furthermore, reliable packets go ahead of unreliable ones on all queues, in particular, the CPU queue. In addition, unreliable packets can be flushed from the net at any time, if some resource they are using (such as buffer space) is needed for a reliable packet. These latter two measures are needed to ensure that the net does not become so heavily loaded with unreliable packets that there is no room for the reliable ones. (It would not make much sense to advertise a "reliable" service, and then to allow the unreliable packets to dominate the network by using most of the network resources. If unreliable packets could grab most of the resources, leaving the "reliable" ones to scavenge for the left-over resources, then it would be virtually inevitable that the service received by the "unreliable" packets would appear, to the users, to be more reliable than the service received by the "reliable" packets. To achieve a true dichotomy between reliable and unreliable service, the reliable packets must be given priority in all respects over the unreliable ones. We should also remember, by the way, that although many protocols combine features of reliability, sequentiality, error control, and flow control, these are not the - 38 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen same, and there is no reason why a network might not offer a reliable but unsequenced service). This sort of network design seems quite reasonable, perhaps more reasonable than the design of any existing network. It would allow for a (presumably inexpensive) class of service ("unreliable") which would be able to use only those network resources not needed by the more reliable (and expensive) class of packets, and which would not suffer any additional delay due to the presence of the protocols which would be needed to ensure reliability. In such a network, unreliable packets might well experience less delay than reliable ones, WHEN THE NETWORK IS LIGHTLY LOADED; WHEN IT IS HEAVILY LOADED, HOWEVER, RELIABLE PACKETS WOULD TEND TO EXPERIENCE THE SMALLER DELAY. If this is the case, it is hard to see how a user could be expected to make a reasonable choice of IP service parameters at all. He may know what his needs are, but we can hardly expect him to know how to map his needs onto particular aspects of the behavior of a particular network component of an internet, especially when the behavior determined by that mapping will vary dynamically with the network loading, and hence with the time of day. Two other peculiarities of the "type of service" feature of the IP are worth mentioning. First, there seems to be no notion of the relation between speed and priority, though in many networks, the priority of a message is the major determinant of its speed. (There are, to be sure, networks which attempt to - 39 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen treat priority solely as "acceptance class", differentiating it completely from considerations of speed. However, we know of no network implementation which has been shown to differentiate SUCCESSFULLY between these two concepts, and there is reason to doubt that this differentiation is even possible in principle.) Second, one of the choices to be made is whether to prefer stream or datagram service. This is a clear example of something that is not based on "abstract parameters of quality of service", but rather on a particular feature of one or two particular networks. Requesting stream service will NOT do what a user might expect it to do, namely set up a stream or virtual circuit through the entire internet. This would require a lengthy connection set-up procedure, involving reservations of resources in the gateways, which resources are to be used only for specific connections. If we are really serious about providing stream service, this is just as important as obtaining stream service within the component networks serving as the Pathways of the internet. Indeed, it is hard to imagine any real use for an internet "stream service" which treats packets as datagrams during most of their lifetime in the internet, and then treats them as stream packets in one or two component networks. It must be remembered that the sort of stream service provided by a network like SATNET is only useful to a user if his data appears at the SATNET interface at fixed periods, synchronized with the scheduling of the stream slots on the satellite channel. If the data must - 40 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen first travel through several datagram networks before reaching SATNET, IT IS VIRTUALLY IMPOSSIBLE THAT THE DATA WILL ARRIVE AT SATNET WITH THE PROPER PERIODICITY to allow it to make proper use of the SATNET stream. Now there are certain specific cases where it might be possible to provide some sort of stream service, say if some data is going from a local network through SATNET to another local network and thence directly to the destination Host. (Though even in this case, some sort of connection set-up and reservation of resources in the gateways between SATNET and the local networks would probably be necessary.) Note, however, that if a user requests this type of service, he is also constraining the types of routes his data can travel. If SATNET is not available, he might not want to use the internet at all at that time. Or he might be willing to tolerate a less optimal route ("half a loaf is better than none"), but might not want "stream service" if the less optimal route has to be used. In no case can a type of service like "stream" be obtained simply through the mapping of "type of service" in the internet onto "type of service" in the component networks. We do not want to have a Network Access Protocol that will need to be infinitely expandable, so that the user can indicate the type of service he wants in each particular network that his data may eventually travel through. For one thing, as the internet becomes larger, so that there are more paths between each possible source and destination, the users will not - 41 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen generally know what set of networks their data will travel through. Since the number of component networks in the internet may be continually increasing, and since we cannot anticipate in advance the features that each new network may offer, it does not really seem reasonable to have to keep adding fields to the IP, to account for particular characteristics of each new component network. Yet this seems inevitable with the current approach. That is, we do not agree with the claim in the IP spec that the type of service field in the IP indicates "abstract parameters". Rather, we think the type of service field has been constructed with certain particular networks in mind, just those networks which are currently in the Catenet, and that the various service fields have no meaning whatsoever apart from the particular "suggested" mappings to protocol features of specific networks given in the spec. (And since these mappings are only "suggested", not required, one might wonder whether the type of service field really has any consistent meaning at all). This situation is perhaps tolerable in a research environment, where most of the users of the internet are explicitly concerned with issues of networking, and willing to try a large number of experiments to see what sort of service they get. One must remember, however, that in a truly operational environment, the average user will not be concerned at all about networking, will not know anything about networking, will not care about networking, and will only want the network to appear transparent - 42 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen to him. In order for such a user to make successful use of the type of service field in a Network Access Protocol, the parameters of the field must be meaningful to him. If they are only meaningful to network experts, the user will never be able to figure out how best to set these parameters. Rather than providing a type of service specification which is nothing but a sort of "linear combination" of the types of service provided by the component networks, the internet ought to offer a small, specific number of service types which are meaningful at the application level. The possible values of internet service type might be "interactive session," "transaction," "file transfer", "packetized speech," and perhaps a few others. The categories should be simple enough so that the user can figure out which category his particular application falls into without needing to know the details of the operation of the internet. The Switches of the internet should take responsibility for sending the data on a route which is capable of providing the requested type of service, and for sending the data through component networks of the internet in a way which maximizes the possibility that the type of service requested will actually be achieved. Of course, in order to do this, we must first answer a couple of hard questions, such as "Exactly what characteristics of service do users want and expect for particular applications?", and "What features must the internet Switches have, and what features must the component networks - 43 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen have, in order to provide service with the necessary characteristics?" In order to give adequate communications service in an operational environment, however, these questions must be given careful consideration by internet designers. To some extent, these questions are difficult research issues, and answering them will require doing some systematic experimentation and instrumentation in the internet. The problem is hard, but unavoidable. The IP's current approach seems aimed at side-stepping these issues, since it places the burden entirely on the user. It tends to give users the illusion that, by properly specifying the bit fields in the IP header, they can tune the internet to provide them with the specific type of service they find most desirable. This is, however, only an illusion. The perspective taken by the current IP seems to be not, "How should the internet be designed so as to provide the needed characteristics of service while providing a simple interface to the user?", but rather, "Taking the current design of the internet as a given, how can we give the user the ability to massage, bend, and twist it so as to get service characteristics which might be close to what he wants?" The former perspective seems much more appropriate than the latter. Although we are not at present prepared to offer an alternative to IP, there are several lessons we would like to draw from this discussion: - 44 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen 1) While an internet Network Access Protocol really does need to contain some field which indicates the desired type of service in a manner which is abstract enough to be mapped to particular protocol features of particular networks, the proper specification of a sufficiently abstract set of parameters is an open and difficult research issue, but one which needs to be studied if an operational internet configuration is ever to give really adequate service to a relatively naive end-user. 2) Providing the requested type of service may require cooperation from all the Switches (perhaps through the routing algorithm), and involves more than just mapping fields from the internet Network Access Protocol to the particular access protocols used by the component networks. If the type of service requested by the user is to be consistently meaningful, then his request must be given UNIFORM treatment by the internet Switches. Different gateways must not be allowed to treat the request differently. 2.4 Special Features The DoD Standard Internet Protocol contains a number of features which, while not strictly necessary in order for a user to get his data delivered, and distinct from the type of service field, do affect to some extent the service a user gets from the - 45 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen internet. Some of the features are worthy of comment, and that is the purpose of this section. 2.4.1 Time to Live The presence of the "time-to-live" field in the Catenet IP seems like a clear example of something that has no place in an access protocol. The IP specification [1] has some contradictory things to say about time-to-live. The user is supposed to set this field to the number of seconds after which he no longer cares to have his information delivered, or something like that. It's far from clear how some user is supposed to make a decision as to what value to set this to. For one thing, although this value is supposed to be represented in units of one second [1, p. 24], there does not appear to be any requirement for the gateways to figure out how many seconds to decrement this value by. The spec actually says that each gateway should decrement this field by at least one, even if it has no idea how much time has actually elapsed [1, p. 40]. Well, a user might ask, is this field represented in seconds or isn't it? What is the point of saying in the spec that it is in seconds, if it is not necessarily in seconds; this will only result in confusion. That is, any attempt by a user to set this field to a reasonable value is likely to have unanticipated consequences. Any attempt to make inferences about internet behavior from the effect that various settings of the time-to-live field will necessarily be unreliable. - 46 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen At any rate, unless the Switches all keep a synchronized clock, there is no real way for them to determine how long a packet has been in the network (or internet), as opposed to how much time it has spent in the Switches, and this difference may be significant if a packet is sent over several long-haul networks with long-delay lines but fast Switches. It's hard to see the point of requiring a user to specify, in the Network Access Protocol, a value which cannot be assigned any consistent meaning. (It's not clear what value this information has anyway; according to the IP spec, "the intention is to cause undeliverable datagrams to be discarded" [1, p. 24]. But a reasonable routing algorithm should cause undeliverable datagrams to be discarded anyway, no matter what value is specified for time-to-live). It seems plain in any case that over the years, Host personnel will begin to tend to set this field to its maximum value anyway. In most implementations, the setting of this field will not be left to the end-user, but will be in the code which implements the IP. Several years from now, no one will remember the importance of setting this field correctly. Eventually, someone will discover that the data he sends to a certain place does not get through, and after months of intensive investigation, it will turn out that his IP is setting too small a value in the time-to-live field, and his packets are dying just before they reach their destination. This will make people tend - 47 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen to use the maximum value as a default, reducing the utility of the information to almost nil. (No one will want to spend the time re-tuning this value to the optimum as the internet configuration expands, causing real packet delays to become longer and longer. In fact, at many Host sites there may not be anyone who can figure out enough of the Host code to be able to re-tune this value.) Time-to-live, while useful for debugging purposes (perhaps), has no real place in an operational system, and hence is not properly part of a Network Access Protocol. If the Switches of a Network Structure want to perform packet life timing functions, in a way which is under the control of a single network administration, and easily modified to reflect changing realities, that is one thing. It is quite a different thing to build this into a Host-level protocol, with a contradictory spec, where it will certainly fall into disuse, or misuse. Protocol features which are only useful (at best) for network experimenters and investigators are bound to cause trouble when invoked at the Host level, as part of a protocol which every Host must implement, and whose implementers may not fully understand the implications of what they are doing. Some of these difficulties have, as their basic cause, the old implicit model of the internet that we discussed in IEN 185. The IP conflates protocol features that properly belong to the - 48 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen Network Access Protocol with features that properly belong to the protocol used internally among the Switches. This sort of conflation, and consequent violation of protocol layering, are inevitable if the gateways are seen as hosts which patch networks together, rather than as Switches in an autonomous Network Structure. 2.4.2 Source Routing The current IP has a feature known as "source routing," which allows each user to specify the sequence of networks that his internet packet is to travel. We mention this primarily as an example of something that a Network Access Protocol in a truly operational environment ought not to have. An acceptable internet routing algorithm ought to distribute the traffic in order to achieve some general goal on an internet-wide basis, such as minimizing delay, maximizing throughput, etc. Any such routing algorithm is subverted if each user is allowed to specify his own route. Much of the routing algorithm's ability to prevent or avoid congestion is also compromised if certain packets are allowed to follow a route pre-determined by some user, even if the routing algorithm determines that best service (either for those packets themselves, or for other packets in the internet) would be obtained if those packets followed a different route. - 49 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen To a certain extent, the presence of the source routing option in the IP is probably a result of the rather poor routing strategy in the present Catenet, and a way of attempting to obtain better service than the routing algorithm can actually provide. The long-term solution to this problem would be to improve the routing algorithm, rather than to subvert it with something that is basically a kludge. We would claim that the existence of any application or service that seems to require the use of source routing is really an indication of some lack or failure in the design of the internet, and a proper long-term solution is to improve the situation by making basic architectural changes in the internet, rather than by grafting on new kludges. Source routing also has its use as an experimental device, allowing tests to be performed which might indicate whether it is really worthwhile to add some new feature or service to the internet. (Although the way in which source routing subverts the basic internet routing algorithm can have disturbing side-effects on the experimental results, which must be properly controlled for.) However, we doubt that any truly useful experiments requiring source routing can be performed by individual users in isolation. Rather, useful experiments would seem to require the cooperation and coordination of the participating users as well as those who are responsible for controlling and maintaining the internet. So it is not clear that there is any true utility to - 50 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen having a source routing option at the level of the Network Access Protocol, thereby giving each and every user the option of using it. In an operational environment, this feature should either be eliminated, or controlled through the use of authorizations, which would cause gateways to discard source-routed packets which lack proper authorization. 2.4.3 Fragmentation and Reassembly One of the few problems which is really specific to an internet whose pathways consist of packet-switching networks is the fact that it is difficult to specify to the user a maximum packet size to use when giving traffic to the internet. If a user's traffic is to go through EVERY component packet-switching network, then the maximum packet size he can use is that of the component network with the smallest maximum packet size. Yet it seems unwise to require that no user ever exceed the maximum packet size of the component network with the smallest maximum packet size. To do so might lead to very inefficient use of other component networks which permit larger packet sizes. If a particular user's traffic does not happen to traverse the component network with the smallest maximum packet size, the restriction really does no good, and only leads to inefficiency. Since, in a large internet, most traffic will probably traverse only a small subset of the component networks, this is quite important. In addition, some Hosts with limited resources might - 51 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen have a high overhead on a per-packet basis, making it quite important to allow them to put larger packets into the internet. This gives rise to the question of, what should an internet Switch do if it must route a packet over a certain Pathway, but that packet is larger than the maximum size of packets that can be carried over that Pathway? The solution that has been adopted in the current Catenet is to allow the internet Switches to "fragment" the packets into several pieces whenever this is necessary in order to send the packet over a Pathway with a small maximum packet size. Each fragment of the original packet is now treated as an independent datagram, to be delivered to the destination Host. It is the responsibility of the destination Host to reassemble the original packet from all the fragments before passing it up to the next highest protocol layer. (If the destination happens to have a high per-packet overhead, too bad.) The IP has several features whose only purpose is to enable this reassembly. These features are extremely general, so that fragments can be further fragmented, ad infinitum, and correct reassembly will still be possible. However, it seems that this feature has not had very much operational testing in the Catenet; gateway implementers seem to be as reluctant to actually implement fragmentation as Host implementers are to implement reassembly. If at least one gateway does do fragmentation, then if some Host does not do reassembly, it cannot, in general, talk - 52 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen to any other Host on the internet. If a source Host knows that a destination Host does not do reassembly, then it can, through IP, indicate to the gateways that they ought not to fragment. However, in that case, any datagrams that are not fragmentable but which must be transmitted over a Pathway with a smaller maximum packet size are simply lost in transit. It should be noted that the procedure of doing reassembly in the destination Host violates the precepts of protocol layering in a basic way. The internet is not transparent to protocol modules in the Hosts, since a datagram put into the internet by a protocol module in the source Host might appear at the destination Host in quite a different form, viz., as a set of fragments. One might try to avoid this conclusion by claiming that what we have been calling "the Host software modules" are really part of a Switch, rather than part of a Host, so that no transparency is violated. One could also claim that a dog has five legs, by agreeing to call its tail a leg. But this would no more make a tail a leg than calling a Host software module "part of the network" makes it so. One of the main advantages of properly layered protocols is the ability it provides to change the network without having to change the Hosts. This is needed if changes to the network are even to be possible, since any change that requires Host software to change is, for all practical purposes, impossible. This suggests that the boundary of the network be drawn at the boundary where changes are - 53 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen possible without coordination among an unlimited number of Host administrations, and the natural place to draw this boundary is around the Switches. While the Switches of a Network Structure can all be under the control of a common administration, the Hosts cannot. This suggests that any violation of protocol layering that is as gross as the need to have Hosts do reassembly is a problem that is to be avoided whenever possible. The problems of writing Host-level software to do reassembly in a reliable manner do not seem to have been fully appreciated. If a Host's resources (such as buffer space, queuing slots, table areas, etc.) are very highly utilized, all sorts of performance sub-optimalities are possible. Without adequate buffer management (see IEN 182), even lock-ups are possible. One must remember that reassembly is not a simple matter of sending the fragments to the next higher level process in proper sequence. The situation is more complex, since the first fragment of a datagram cannot be sent up to the next higher protocol level until all the fragments of that datagram are received. If buffers are not pre-allocated at the destination Host, then fragments of some datagrams may need to be discarded to ensure that there is room to hold all the fragments of some other datagram; otherwise "reassembly lockup" is possible. If the internet gateways really did a large amount of fragmentation, so that Hosts needed to do a large amount of reassembly, this would almost certainly give rise to a variety of peculiar performance - 54 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen problems and phasing effects which could make the recently discovered "silly window syndrome" look quite benign. Unfortunately, it is hard to gain an appreciation of these sorts of problems until one has personally encountered them, at which point it is often too late to do anything about them. Performance considerations (as opposed simply to considerations of functionality) would seem to indicate that fragmentation and reassembly be avoided whenever possible. Note that performance problems associated with reassembly might crop up suddenly at any time in the life of the internet, as some Host which rarely received fragments in the past suddenly finds itself bombarded with them, possibly due to a new application. Since this sort of effect is notoriously difficult to test out in advance, one would expect potential problems to be lying in wait. Problems like these tend to crop up at a time when the Host administration has no one available who understands and can modify the Host software, which means that such problems can be very intransigent and difficult to remedy. Of course, problems in Host networking software are usually blamed on the network (i.e., on the Switches), which also does not help to speed problem resolution. One way to remove this sort of problem from the Host domain is to have the destination Switches themselves do any necessary reassembly before passing a datagram on to its destination Host. - 55 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen This has the advantage that problems which arise will fall under the domain of the Network administration, which is more likely to be able to deal with them than are the various Host administrations. However, this really does not simplify the situation, or reduce the amount of performance sub-optimalities that we might be faced with; it just takes the same problems and puts them somewhere else. ARPANET IMPs do fragmentation (though only at the source IMP) and reassembly at the destination IMP, and this has turned out to be quite a tricky and problem-strewn mechanism. Other approaches should be investigated. Of course, one possible way around fragmentation is to adopt a policy of not routing any packets over Pathways which cannot handle packets of that size. If there are several possible routes between source and destination, which have similar characteristics except for the fact that one of them has a maximum packet size which is too small, the most efficient means of handling this problem might just be to avoid using the route which would require fragmentation. Even if this means taking a slightly longer route to the destination, the extra delay imposed during internet transit might be more than compensated for by the reduction in delay that would be obtained by not forcing the destination Host to do reassembly. Of course, this scheme requires interaction with routing, but as long as there are a small number of possible maximum packet sizes, this scheme is not difficult to implement (at least, given a reasonable routing algorithm). - 56 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen Unfortunately, it might be the case that there just is no route at all to a particular destination, or else no reasonable route, which does not utilize a Pathway whose maximum packet size is "too small." In this case, there seems no way around fragmentation and reassembly. However, a scheme which is worth considering is that of doing hop-by-hop fragmentation and reassembly within the internet. That is, rather than having reassembly done at the destination (Switch or Host), it is possible to do reassembly at the Switch which is the exit point from a component network which has an unusually small packet size. Datagrams would be fragmented upon entry to such networks, and reassembled upon exit from them, with no burden on either the destination Switch or the destination Host. The fact that fragments would never travel more than one hop without reassembly ameliorates the performance problems somewhat, since the amount of time a partially reassembled datagram might have to be held would be less, in general, than if reassembly were done on an end-end basis. A strategy of doing hop-by-hop reassembly and fragmentation also allows more efficient use of the internet's Pathways in certain cases. One problem with the end-end strategy is the essential "randomness" of its effects. Consider, for example, a large packet which must traverse several networks with large maximum packet sizes, and then one network with a small maximum packet size. The current method of doing fragmentation and - 57 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen reassembly allows the packet to remain large throughout the networks that can handle it, fragmenting it only when it reaches its final hop. This seems efficient enough, but consider the case where the FIRST internet hop is the network with the smallest maximum packet size, and the remaining hops are networks with large maximum packet sizes. The current strategy then causes a very inefficient use of the internet, since the packet must now travel fragmented through ALL the networks, including the ones which would allow the larger packet size. If some of these networks impose constraints on a per-packet basis (which might either be flow control constraints, or monetary constraints based on per-packet billing), this inefficiency can have a considerable cost. Hop-by-hop reassembly, on the other hand, would allow the large packet to be reassembled and to travel through the remaining networks in the most cost-effective manner. Such a strategy is most consonant with our general thesis that an efficient and reliable internet must contain Switches which are specifically tuned to the characteristics of the individual Pathways. It also removes the problem from the Host domain, making the system more consonant with the precepts of protocol layering. There is, unfortunately, one situation in which hop-by-hop fragmentation cannot work. If the Pathway between some destination Host and the destination Switch has a small maximum packet size, so that the destination Switch must fragment - 58 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen datagrams intended for that Host, then reassembly must be done by the Host itself, since there is no Switch at the other end of the Pathway to do the reassembly. This seems to mean that Hosts whose "home networks" have unusually small maximum packet sizes will be forced to implement the ability to perform reassembly, and must tolerate any resultant performance disadvantages. 2.5 Flow Control The topic of "flow control" or "congestion control" (we shall be employing these terms rather interchangeably, ignoring any pedantic distinctions between them) breaks down naturally into a number of sub-topics. In this section we shall be concerned with only one such sub-topic, namely, how should the Switches of the Network Structure enforce flow control restrictions on the Hosts? We shall not consider here the issue of how the Switches should do internal flow control, or what protocols they need to run among themselves to disseminate flow control information, but only the issue of how the results of any internal flow control algorithm should be fed back to the hosts. The IP is a rather unusual Network Access Protocol, in that it does not have any flow or congestion control features at all. This makes it very different from most other Network Access Protocols, such as 1822 or X.25, which do have ways of imposing controls on the rate at which users can put data into the network. The IP, on the other hand, is supposed to be a - 59 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen "datagram protocol", and therefore (?) is not supposed to impose any flow or congestion control restrictions on the rate at which data can be sent into the internet. In this section, we will discuss whether this is appropriate, and whether the "therefore" of the previous sentence is really correctly used. The issue of how flow or congestion control restrictions ought to be passed back to a Host, or more generally, how a Network Structure ought to enforce its congestion control restrictions, is a tricky issue. Particularly tricky is the relation between datagram protocols and flow control. Datagrams are sometimes known (especially with reference to the ARPANET) as "uncontrolled packets," which tends to suggest that no flow control should be applied to them. This way of thinking may be a holdover from the early days of the ARPANET, when it was quite lightly loaded. In those days, the flow control which the ARPANET imposes was much too strict, holding the throughput of particular connections to an unreasonably low value. Higher throughput could often be obtained by ignoring the controls, and just sending as much traffic as necessary for a particular application. Since the network was lightly loaded, ignoring the controls did not cause much congestion. Of course, this strategy breaks down when applied to the more heavily loaded ARPANET of today. Too much uncontrolled traffic can cause severe congestion, which reduces throughput for everybody. Therefore - 60 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen many people now tend to recognize the need to control the uncontrolled packets, if we may be forgiven that apparent contradiction. Clearly, there is some tension here, since it makes little sense to regard the same traffic as both "controlled" and "uncontrolled." If a Network Access Protocol is developed on the assumption that it should be a "datagram protocol", and hence need not apply any controls to the rate at which data can be transferred, it will not be an effective medium for the enforcement of flow control restrictions at the host-network access point. If congestion begins to become a problem, so that people gradually begin to realize the importance of congestion control, they will find that the Network Access Protocol gives them no way to force the Hosts to restrict their traffic when that is necessary. The probable result of this scenario would be to try to develop a scheme to get the congestion control information to the Hosts in a way that bypasses the Network Access Protocol. This is our "logical reconstruction" of the current situation in the Catenet. When gateways think that there is congestion, they send "source quench" packets to the Hosts themselves, and the Hosts are supposed to do something to reduce the congestion. This source quench mechanism should be recognized for what it is, namely a protocol which is run between EVERY host and EVERY Switch (including intermediate Switches, not just source Switches) within a Network Structure, and which completely bypasses the - 61 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen Network Access Protocol (IP). This violates protocol layering in a very basic way, since proper layering seems to imply that a source Host should have to run a protocol with a source Switch only, not with every Switch in the network. Of course, the fact that some mechanism appears to violate the constraints of protocol layering is not necessarily a fatal objection to it. However, given the present state of the art of flow control techniques, which is quite primitive, flow control procedures must be designed in a way that permits them to be easily modified, or even completely changed, as we learn more about flow control. We must be able to make any sort of changes to the internal flow control mechanism of a Network Structure without any need to make changes in Host-level software at the same time. ARPANET experience indicates quite clearly that changes which would be technically salutary, but which require Host software modifications, are virtually impossible to make. Host personnel cannot justify large expenditures of their own to make changes for which they perceive no crucial need of their own, just because network personnel believe the changes would result in better network service. If we want to be able to experiment with different internal flow control techniques in the internet, then we must provide a clean interface between the internal flow control protocols, and the way in which flow control information is fed back to the Hosts. We must define a relatively simple and straightforward interface by which a source - 62 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen Switch can enforce flow control restrictions on a Host, independently of how the source Switch determines just what restrictions to enforce. The way in which the Switches determine these restrictions can be changed as we learn more about flow control, but the Host interface will remain the same. It is not clear that the source quench mechanism has been generally recognized as a new sort of protocol, which bypasses the usual Network Access Protocol for the internet (IP). One reason that it may seem strange to dignify this mechanism with the name of "protocol" is that no one really knows what a source quench packet really means, and no one really knows what they are supposed to do when they get one. So generally, they are just ignored, and the "procedure" of ignoring a control packet seems like a very degenerate case of a protocol. Further, the source quench mechanism is a protocol which Host software implementers seem to feel free to violate with impunity. No implementer could decide to ignore the protocols governing the form of addresses in the internet, or he would never be able to send or receive data. Yet there is no penalty for ignoring source quench packets, although violating the flow control part of the internetting protocol seems like something that really ought to be prohibited. (We have even heard rumors of Host software implementers who have decided to increase their rate of traffic flow into the internet upon receiving a source quench packet, on the grounds that if they are receiving source quench packets, some of their traffic - 63 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen is not getting through, and therefore they had better retransmit their traffic right away.) We have spoken of a source Switch needing to be able to ENFORCE flow control restrictions, by which we mean that when a source Switch determines that a certain source Host ought to reduce its rate of traffic, the Switch will REFUSE to accept traffic at a faster rate. Proper flow control can never be accomplished if we have to rely either on the good will or the good sense of Host software implementers. (Remember that Host software implementations will continue for years after the internet becomes operational, and future implementers may not be as conversant as current implementers with networking issues). This means a major change to the IP concept. Yet it seems to make much more sense to enhance the Catenet Network Access Protocol to allow for flow control than to try to bypass the Network Access Protocol entirely by sending control information directly from intermediate Switches to a Host which is only going to ignore it. We will not discuss internal flow control mechanisms here, except to say that we do not believe at all in "choke packet" schemes, of which the source quench mechanism is an example. Eventually, we will propose an internal congestion control scheme for the internet, but it will not look at all like the source quench mechanism. (Chapters 5 and 6 of [2] contain some - 64 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen interesting discussions of congestion control in general, and of choke packet schemes in particular.) It appears that some internet workers are now becoming concerned with the issue of what to do when source quench packets are received, but this way of putting the question is somewhat misdirected. When you get some information, and you still don't know what decision to make or what action to take, maybe the problem is not so much in the decision-making process as it is in the information. The proper question is not, "what should we do when we get source quench packets?", but rather "what should we get instead of source quench packets that would provide a clear and meaningful indication as to what we should do? Does this mean that the internet Network Access Protocol should not really be a datagram protocol? To some extent, this is merely a terminological issue. There is no reason why a protocol cannot enforce congestion or flow control without also imposing reliability or sequentiality, or any other features that may unnecessarily add delay or reduce throughput. Whether such a protocol would be called a "datagram protocol" is a matter of no import. It is worth noting, though, that the Network Access Protocol of AUTODIN II (SIP), while officially known as a datagram protocol, does impose and enforce flow control restrictions on its hosts. - 65 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen The only real way for a source Switch to enforce its flow control restrictions on a source Host is simply for the Switch to REFUSE packets from that Host if the Host is sending too rapidly. At its simplest, the Switch could simply drop the packets, with no further action. A somewhat more complex procedure would have the Switch inform the Host that a packet had been dropped. A yet more complex procedure would tell the Host when to try again. Even more complex schemes, like the windowing scheme of X.25, are also possible. To make any of these work, however, it seems that a source Switch (gateway) will have to maintain Host-specific traffic information, which will inevitably place a limit on the number of Hosts that can be accessing a source Switch simultaneously. Yet this seems inevitable if we are to take seriously the need for flow control. At any rate, the need for flow control really implies the need for the existence of such limits. 2.6 Pathway Access Protocol Instrumentation Fault isolation in an internet environment is a very difficult task, since there are so many components, and so many ways for each to fail, that a performance problem perceived by the user may be caused by any of a thousand different scenarios. Furthermore, by the time the problem becomes evident at the user level, information as to the cause of the problem may be long gone. Effective fault isolation in the internet environment will - 66 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen require proper instrumentation in ALL internet components, including the Hosts. We will end this paper with a few remarks about the sort of instrumentation that Hosts should have, to help in fault-isolation when there is an apparent network problem. We have very often found people blaming the ARPANET for lost data, when in fact the problem is entirely within the host itself. The main source of this difficulty is that there often is no way for host personnel to find out what is happening within the host software. Sometimes host personnel will attempt to deduce the source of the apparent problem by watching the lights on the IMP interface blink, and putting that information together with the folklore that they have heard about the network (which folklore is rarely true). Our ARPANET experience shows quite clearly that this sort of fault-isolation procedure just is not useful at all. What is really needed is a much more complex, objective, and SYSTEMATIC form of instrumentation, which unfortunately is much more difficult to do than simply looking at the blinking lights. Some sorts of essential instrumentation are quite specific to the sort of Network Access Protocol or Pathway Access Protocol that is being used. For example, users of the ARPANET often complain that the IMP is blocking their host for an excessive amount of time. By itself, this information is not very useful, since it is only a symptom which can have any of a large number of causes. In particular, the host itself may be forcing the IMP to block by attempting to violate ARPANET flow control - 67 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen restrictions. One sort of instrumentation which would be useful for the host to have is a way of keeping track of the total time it is blocked by the IMP, with the blocking time divided into the following categories: 1) Time blocked between messages. 2) Time blocked between the leader of a message and the data of the message. 3) Time blocked between packets. 4) Time blocked while attempting to send a multi-packet message (a subset of 2). 5) Time blocked during transmission of the data portion of a packet. 6) Time blocked while attempting to transmit a datagram (a subset of 2). While this information might be very non-trivial for a host to gather, it does not help us very much in fixing the problem just to know that "the IMP is blocking" unless we can get a breakdown like this. In addition, it is useful to have those categories further broken down by destination Host, in case the blocking is specific to some particular set of hosts. - 68 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen Additional useful information has to do with the 1822 reply messages. What percentage of transmitted messages are replied to with RFNMs? with DEADs? with INCOMPLETEs? This should also be broken down by destination host. In fact, it would be useful to keep track of the number of each possible 1822 IMP-host control message that is received. When problems arise, it may be possible to correlate this information with the problem symptoms. The basic idea here should be clear -- besides just telling us that "the network isn't taking packets fast enough", host personnel should be able to tell us under what conditions the network is or is not taking packets, and just what "fast enough" means. If a host is also running an access protocol other than (or in addition to) 1822, there will be specific measurements relevant to the operation of that protocol, but in order to say just what they are, one must be familiar with those particular protocols. (Again we see the effects of particular Pathway characteristics, this time on the sort of instrumentation needed for good fault isolation.) In general, whenever any protocol module is designed and implemented, the designer AND implementer (each of whom can contribute from a different but equally valuable perspective) should try to think of anything the protocol or the software module which implements it might do which could hold up traffic flow (e.g., flow control windows being closed, running out of sequence number space, failing to get timely acknowledgments, process getting swapped out, etc.), - 69 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen and should be able to gather statistics (say, average and maximum values of the amount of time data transfer is being held up for each possible cause) which tell us how the protocol module is performing. If a protocol requires (or allows) retransmissions, rate of retransmission is a very useful statistic, especially if broken down by destination host. Hosts should be able to supply statistics on the utilization of host resources. Currently, for example, many hosts cannot even provide any information about their buffer utilization, or about the lengths of the various queues which a packet must traverse when traveling (in either direction) between the host and the IMP. Yet very high buffer utilization or very long queues within the host may be a source of performance problems. When a packet has to go through several protocol modules within a host (say, from TELNET to TCP to IP to 1822), the host should be able to supply statistics on average and maximum times it takes for a packet to get through each of these modules. This can help in the discovery of unexpected or unanticipated bottlenecks within the host. (For example, packets may take an unexpectedly long amount of time to get through a certain module because the module is often swapped out. This is something that is especially likely to happen some years after the host software is initially developed, when no one remembers anymore that the host - 70 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen networking software is supposed to have a high priority. This sort of instrumentation can be quite tricky to get just right, since one must make sure that there is no period of time that slips between the time-stamps). The offered and obtained throughputs through each protocol module are also useful statistics. In addition, if a host can ever drop packets, it should keep track of this. It should be able to provide information as to what percentage of packets to (or from) each destination host (or source host) were dropped, and this should be further broken down into categories indicating why the packets were dropped. (Reasons for hosts' dropping packets will vary from implementation to implementation). Note that this sort of instrumentation is much harder to implement if we are using datagram protocols than if we are using protocols with more control information, because much of this instrumentation is based on sent or received control information. The less control information we have, the less we can instrument, which means that fault-isolation and performance evaluation become much harder. This seems to be a significant, though not yet widely-noticed, disadvantage of datagram protocols. Host personnel may want to consider having some amount of instrumentation in removable packages, rather than in permanently resident code. This ability may be essential for efficiency reasons if the instrumentation code is either large or slow. In - 71 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen that case, it might be necessary to load it in only when a problem seems evident. Instrumentation should also have the ability to be turned on and off, so that it is possible to gather data over particular time windows. This is necessary if the instrumentation is to be used as part of the evaluation of an experiment. - 72 - IEN 187 Bolt Beranek and Newman Inc. Eric C. Rosen REFERENCES 1. "DOD Standard Internet Protocol," COMPUTER COMMUNICATION REVIEW, October 1980, pp. 12-51. 2. "ARPANET Routing Algorithm Improvements," BBN Report No. 4473, August 1980. - 73 - -------